﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 우선순위 큐
    /// </summary>
    /// <typeparam name="T"></typeparam>
    class PriorityQueue<T>
    {
        private T[] heap;
        private int size = 0;
        private IComparer<T> comparer;
        public int Count { get { return size; } }
        public bool Empty { get { return size == 0; } }
        private bool max = false;
        public PriorityQueue()
            : this(1024, false, Comparer<T>.Default)
        { }
        public PriorityQueue(int maxSize) 
            : this(maxSize, false, Comparer<T>.Default)
        { }
        public PriorityQueue(int maxSize, bool max)
            : this(maxSize, max, Comparer<T>.Default)
        { }
        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="maxSize"><최대 사이즈/param>
        public PriorityQueue(int maxSize, bool max, IComparer<T> comparer)
        {
            heap = new T[maxSize];
            this.max = max;
            this.comparer = comparer;
        }

        private void PushMax(T x)
        {
            //자기 노드
            int self = size++;
            while (self > 0)
            {
                //부모 노드
                int parent = (self - 1) / 2;
                //부모 노드의 값이 입력값보다 작으면
                if (comparer.Compare(heap[parent], x) > 0)
                {
                    break;
                }
                else
                {
                    heap[self] = heap[parent]; //부모 노드를 내리고 자기노드가 올라감
                    self = parent;
                }
            }
            heap[self] = x;
        }
        private void PushMin(T x)
        {
            //자기 노드
            int self = size++;
            while (self > 0)
            {
                //부모 노드
                int parent = (self - 1) / 2;
                //부모 노드의 값이 입력값보다 작으면
                if (comparer.Compare(heap[parent], x) < 0)
                {
                    break;
                }
                else
                {
                    heap[self] = heap[parent]; //부모 노드를 내리고 자기노드가 올라감
                    self = parent;
                }
            }
            heap[self] = x;
        }
        public void Push(T x)
        {
            if (max)
            {
                PushMax(x);
            }
            else
            {
                PushMin(x);
            }
        }


        private T PopMin()
        {
            //최소값
            T ret = heap[0];
            //루트로 가져올 값
            T x = heap[--size];
            int self = 0;
            //자식 노드를 검사
            while (self * 2 + 1 < size)
            {
                int a = self * 2 + 1;//왼쪽
                int b = self * 2 + 2;//오른쪽 자식
                if (b < size && comparer.Compare(heap[b], heap[a]) < 0)
                {
                    a = b;
                }
                //a로 작업 값을 가져와 x와 비교
                if (comparer.Compare(heap[a], x) >= 0)
                {
                    break;
                }
                //그 다음 자식을 비교
                heap[self] = heap[a];
                self = a;
            }
            heap[self] = x;
            return ret;
        }
        private T PopMax()
        {
            //최소값
            T ret = heap[0];
            //루트로 가져올 값
            T x = heap[--size];
            int self = 0;
            //자식 노드를 검사
            while (self * 2 + 1 < size)
            {
                int a = self * 2 + 1;//왼쪽
                int b = self * 2 + 2;//오른쪽 자식
                if (b < size && comparer.Compare(heap[b], heap[a]) > 0)
                {
                    a = b;
                }
                //a로 작업 값을 가져와 x와 비교
                if (comparer.Compare(heap[a], x) <= 0)
                {
                    break;
                }
                //그 다음 자식을 비교
                heap[self] = heap[a];
                self = a;
            }
            heap[self] = x;
            return ret;
        }
        public T Pop()
        {
            if (max)
            {
                return PopMax();
            }
            else
            {
                return PopMin();
            }
        }
    }
}
